A problem in many communication systems is the formation of echos. Echo cancellers have traditionally been employed to cancel the echos.
There are two principle types of echo cancellers, the network echo canceller, and the acoustic echo canceller. Network echo cancellers, which are also known in the arts as line echo cancellers, may cancel echos on networks, such as the Public Switched Telephone Network (PSTN). Echos may occur in such networks due to 2-wire/4-wire conversions and other impedance mismatches. Acoustic echo cancellers may cancel echos resulting from feedback or singing between speakers and microphones. Such echos may occur in cell phones, other portable radio communication devices, teleconferencing equipment, and in hands-free mobile telephony devices.
At least conceptually, both network and acoustic echo cancellers may operate on the principle “to remove an echo, subtract it”. The echo canceller may model and estimate the echo, often with the use of an adaptive filter, and then subtract the estimated echo from an actual echo that is resident in the outgoing transmission signal. Reducing the echo may improve the quality of the data or speech that is exchanged over the communication link.
One problem that may present itself in the field of echo cancellation is sparseness of a channel. The term sparseness may imply that the initial delay uncertainty of the impulse response is much longer than the impulse response itself.
FIG. 1 shows an example of a sparse impulse response that may be observed in an echo path. The amplitude of the impulse response is plotted on the y-axis and progression of time is plotted on the x-axis. As shown, there may be a relatively large and uncertain initial delay prior to the impulse response. During this initial delay, the amplitude remains essentially zero. Then, the impulse response may occur. The amplitude of the impulse response may initially achieve a peak value, and then gradually dissipate over time, until the amplitude again becomes zero. The duration of the impulse response is sometimes referred to in the arts as the dispersive region. It is the dispersive region that may contain the information of most relevance for adapting filter coefficients of echo cancellers.
In a sparse channel, the initial delay may last for a much longer period of time than the dispersive region. As one example, the initial delay may last on the order of 128 milliseconds (msec), while the dispersive region may last in the range of 4-20 msec. Traditionally, unnecessarily long filter lengths have been employed in echo cancellation in order to accommodate for the initial delay. However, a significant number of the filter coefficients or taps that correspond in time to the initial delay may have values that are essentially zero or otherwise non-contributing. In the case of a 128 msec delay line, with an 8 kh sampling rate, a majority of 1024 coefficients may essentially be zero. For example, only about 100-200 of the coefficients may be significant.
Now, there are a number of potential drawbacks to employing such long adaptive filters. One drawback is that the filters may be slow to adapt. The speed at which the filters adapt may be inversely proportional to, or at least inversely related to, the number of adaptable filter coefficients. Slower convergence may adversely affect the quality of the data. Other drawbacks are that significant computation may be needed to adapt a long filter and significant memory may be needed to store the coefficients. Yet another drawback is that the coefficients may have noisy weights. The noise of the adaptive coefficients may be proportional to, or at least related to, the number of adaptable filter coefficients. Likewise, there are a number of potential advantages to reducing the filter length. The potential advantages may include faster convergence, less noise, and an overall reduction in the memory to store the coefficients and the amount of computation to adapt the coefficients.
There has heretofore been much effort to reduce the length of the adaptive filters employed in echo cancellers, while still allowing relatively long initial and uncertain delays. Various efforts are discussed in the following references:    (1) D. L. Duttweiler, “Subsampling to Estimate Delay with Application to Echo Canceling” IEEE Trans. on Acoustics, Speech and Signal Processing, Vol. ASSP-31, No. 5, pp. 1090-1099, October 1983.    (2) S. Hosur and A. H. Tewfik, “Wavelet Transform Domain Adaptive FIR Filtering,” IEEE Trans. on Signal Processing, Vol. 45, No. 3, pp. 617-629, March 1997.    (3) M. Doroslovacki and H. Fan, “On-line Identification of Echo-path Impulse Responses by Haar-Wavelet-Based Adaptive Filter”, Proc. IEEE Conf. on Acoustics, Speech and Signal Processing, pp. 1065-1068, 1995.    (4) K. C. Ho and S. D. Blunt, “Rapid Identification of a Sparse Impulse Response Using an Adaptive Algorithm in the Haar Domain” IEEE Trans. on Signal Processing, Vol. 51, No. 3, pp. 628-638, March 2003.
The inventors have developed new and useful methods and apparatus that they hope will greatly advance the arts of modeling sparse impulse responses and canceling echos.